Metric and trigonometric pruning for clustering of uncertain data in 2D geometric space.

Accelerating probabilistic frequent itemset mining a model%2Dbased approach.

Managing uncertainty of XML schema matching.
Abstract — Despite of advances in machine learning technologies, a schema matching result between two database schemas (e.g., those derived from COMA++) is likely to be imprecise. In particular, numerous instances of “possible mappings ” between the schemas may be derived from the matching result. In this paper, we study the problem of managing possible mappings between two heterogeneous XML schemas. We observe that for XML schemas, their possible mappings have a high degree of overlap. We hence propose a novel data structure, called the block tree, to capture the commonalities among possible mappings. The block tree is useful for representing the possible mappings in a compact manner, and can be generated efficiently. Moreover, it supports the evaluation of probabilistic twig query (PTQ), which returns the probability of portions of an XML document that match the query pattern. For users who are interested only in answers with k-highest probabilities, we also propose the top-k PTQ, and present an efficient solution for it. The second challenge we have tackled is to efficiently generate possible mappings for a given schema matching. While this problem can be solved by existing algorithms, we show how to improve the performance of the solution by using a divide-andconquer approach. An extensive evaluation on realistic datasets show that our approaches significantly improve the efficiency of generating, storing, and querying possible mappings. I.
Anonymous Fuzzy Identity%2DBased Encryption for Similarity Search.

Mining uncertain data with probabilistic guarantees.

Oblivious Transfer with Access Control  Realizing Disjunction without Duplication.

Oblivious Transfer with Access Control  Realizing Disjunction without Duplication.

S%2DOLAP an OLAP system for analyzing sequence data.

Non%2Dhomogeneous generalization in privacy preserving data publishing.

Clustering Uncertain Data Using Voronoi Diagrams and R%2DTree Index.
whose locations are described by probability density functions (pdf). We show that the UK-means algorithm, which generalises the k-means algorithm to handle uncertain objects, is very inefficient. The inefficiency comes from the fact that UK-means computes expected distances (ED) between objects and cluster representatives. For arbitrary pdf’s, expected distances are computed by numerical integrations, which are costly operations. We propose pruning techniques that are based on Voronoi diagrams to reduce the number of expected distance calculation. These techniques are analytically proven to be more effective than the basic bounding-box-based technique previously known in the literature. We then introduce an R-tree index to organise the uncertain objects so as to reduce pruning overheads. We conduct experiments to evaluate the effectiveness of our novel techniques. We show that our techniques are additive and, when used in combination, significantly outperform previously known methods.
Clustering Uncertain Data Using Voronoi Diagrams and R%2DTree Index.
whose locations are described by probability density functions (pdf). We show that the UK-means algorithm, which generalises the k-means algorithm to handle uncertain objects, is very inefficient. The inefficiency comes from the fact that UK-means computes expected distances (ED) between objects and cluster representatives. For arbitrary pdf’s, expected distances are computed by numerical integrations, which are costly operations. We propose pruning techniques that are based on Voronoi diagrams to reduce the number of expected distance calculation. These techniques are analytically proven to be more effective than the basic bounding-box-based technique previously known in the literature. We then introduce an R-tree index to organise the uncertain objects so as to reduce pruning overheads. We conduct experiments to evaluate the effectiveness of our novel techniques. We show that our techniques are additive and, when used in combination, significantly outperform previously known methods.
Efficient Skyline Evaluation over Partially Ordered Domains.
Although there has been a considerable body of work on skyline evaluation in multidimensional data with totally ordered attribute domains, there are only a few methods that consider attributes with partially ordered domains. Existing work maps each partially ordered domain to a total order and then adapts algorithms for totallyordered domains to solve the problem. Nevertheless these methods either use stronger notions of dominance, which generate false positives, or require expensive dominance checks. In this paper, we propose two new methods, which do not have these drawbacks. The first method uses an appropriate mapping of a partial order to a total order, inspired by the lattice theorem and an off-the-shelf skyline algorithm. The second technique uses an appropriate storage and indexing approach, inspired by column stores, which enables efficient verification of whether a pair of objects are incompatible. We demonstrate that both our methods are up to an order of magnitude more efficient than previous work and scale well with different problem parameters, such as complexity of partial orders.
Proceedings of the 18th ACM Conference on Information and Knowledge Management

XML Data Integration Using Fragment Join.
Abstract. We study the problem of answering XML queries over multiple data sources under a schema-independent scenario where XML schemas and schema mappings are unavailable. We develop the fragment join operator — a general operator that merges two XML fragments based on their overlapping components. We formally define the operator and propose an efficient algorithm for implementing it. We define schema-independent query processing over multiple data sources and propose a novel framework to solve this problem. We provide theoretical analysis and experimental results that show that our approaches are both effective and efficient. 1
Privacy%2DPreserving Clustering with High Accuracy and Low Time Complexity.
Abstract. This paper proposes an efficient solution with high accuracy to the problem of privacy-preserving clustering. This problem has been studied mainly using two approaches: data perturbation and secure multiparty computation. In our research, we focus on the data perturbation approach, and propose an algorithm of linear time complexity based on 1-d clustering to perturb the data. Performance study on real datasets from the UCI machine learning repository shows that our approach reaches better accuracy and hence lowers the distortion of clustering result than previous approaches. 1
Naive Bayes Classification of Uncertain Data.

E%2Dgovernment Data Interoperability Framework in Hong Kong.
Since its first release in 1998, the Digital 21 Strategy has been serving the blueprint for Hong Kong to develop the information and communications technology infrastructure. With government leadership as an important component, the Strategy has put forward the development of an e-government that can realize one-stop delivery of public electronic services. In 2003, Hong Kong Government has launched the Interoperability Framework (IF) as an e-government initiative to facilitate implementation of cross-department joined-up government services. IF comprises two parts: (1) definition of a set of recommended technical specifications as a single point of reference for departments and contractors to implement joined-up projects, (2) a framework for formulating and managing XML message standards for G2G and G2B data exchange. This paper discusses about the second part of the IF, mainly on the XML Schema and Design Guide, and its reallife applications.
Secure kNN computation on encrypted databases.
Service providers like Google and Amazon are moving into the SaaS (Software as a Service) business. They turn their huge infrastructure into a cloud-computing environment and aggressively recruit businesses to run applications on their platforms. To enforce security and privacy on such a service model, we need to protect the data running on the platform. Unfortunately, traditional encryption methods that aim at providing “unbreakable ” protection are often not adequate because they do not support the execution of applications such as database queries on the encrypted data. In this paper we discuss the general problem of secure computation on an encrypted database and propose a SCONEDB (Secure Computation ON an Encrypted DataBase) model, which captures the execution and security requirements. As a case study, we focus on the problem of k-nearest neighbor (kNN) computation on an encrypted database. We develop a new asymmetric scalar-product-preserving encryption (ASPE) that preserves a special type of scalar product. We use APSE to construct two secure schemes that support kNN computation on encrypted data; each of these schemes is shown to resist practical attacks of a different background knowledge level, at a different overhead cost. Extensive performance studies are carried out to evaluate the overhead and the efficiency of the schemes.
Scalable skyline computation using object%2Dbased space partitioning.
The skyline operator returns from a set of multi-dimensional objects a subset of superior objects that are not dominated by others. This operation is considered very important in multi-objective analysis of large datasets. Although a large number of skyline methods have been proposed, the majority of them focuses on minimizing the I/O cost. However, in high dimensional spaces, the problem can easily become CPU-bound due to the large number of computations required for comparing objects with current skyline points while scanning the database. Based on this observation, we propose a dynamic indexing technique for skyline points that can be integrated into state-of-the-art sort-based skyline algorithms to boost their computational performance. The new indexing and dominance checking approach is supported by a theoretical analysis, while our experiments show that it scales well with the input size and dimensionality not only because unnecessary dominance checks are avoided but also because it allows efficient dominance checking with the help of bitwise operations.
Scalable skyline computation using object%2Dbased space partitioning.
The skyline operator returns from a set of multi-dimensional objects a subset of superior objects that are not dominated by others. This operation is considered very important in multi-objective analysis of large datasets. Although a large number of skyline methods have been proposed, the majority of them focuses on minimizing the I/O cost. However, in high dimensional spaces, the problem can easily become CPU-bound due to the large number of computations required for comparing objects with current skyline points while scanning the database. Based on this observation, we propose a dynamic indexing technique for skyline points that can be integrated into state-of-the-art sort-based skyline algorithms to boost their computational performance. The new indexing and dominance checking approach is supported by a theoretical analysis, while our experiments show that it scales well with the input size and dimensionality not only because unnecessary dominance checks are avoided but also because it allows efficient dominance checking with the help of bitwise operations.
An Audit Environment for Outsourcing of Frequent Itemset Mining.
Finding frequent itemsets is the most costly task in association rule mining. Outsourcing this task to a service provider brings several benefits to the data owner such as cost relief and a less commitment to storage and computational resources. Mining results, however, can be corrupted if the service provider (i) is honest but makes mistakes in the mining process, or (ii) is lazy and reduces costly computation, returning incomplete results, or (iii) is malicious and contaminates the mining results. We address the integrity issue in the outsourcing process, i.e., how the data owner verifies the correctness of the mining results. For this purpose, we propose and develop an audit environment, which consists of a database transformation method and a result verification method. The main component of our audit environment is an artificial itemset planting (AIP) technique. We provide a theoretical foundation on our technique by proving its appropriateness and showing probabilistic guarantees about the correctness of the verification process. Through analytical and experimental studies, we show that our technique is both effective and efficient. 1.
Security and Integrity in Outsourcing of Data Mining.

Clustering Uncertain Data Using Voronoi Diagrams.
whose locations are described by probability density functions (pdf). We show that the UK-means algorithm, which generalises the k-means algorithm to handle uncertain objects, is very inefficient. The inefficiency comes from the fact that UK-means computes expected distances (ED) between objects and cluster representatives. For arbitrary pdf’s, expected distances are computed by numerical integrations, which are costly operations. We propose pruning techniques that are based on Voronoi diagrams to reduce the number of expected distance calculation. These techniques are analytically proven to be more effective than the basic bounding-box-based technique previously known in the literature. We then introduce an R-tree index to organise the uncertain objects so as to reduce pruning overheads. We conduct experiments to evaluate the effectiveness of our novel techniques. We show that our techniques are additive and, when used in combination, significantly outperform previously known methods.
Mining preferences from superior and inferior examples.
Mining user preferences plays a critical role in many important applications such as customer relationship management (CRM), product and service recommendation, and marketing campaigns. In this paper, we identify an interesting and practical problem of mining user preferences: in a multidimensional space where the user preferences on some categorical attributes are unknown, from some superior and inferior examples provided by a user, can we learn about the user’s preferences on those categorical attributes? We model the problem systematically and show that mining user preferences from superior and inferior examples is challenging. Although the problem has great potential in practice, to the best of our knowledge, it has not been explored systematically before. As the first attempt to tackle the problem, we propose a greedy method and show that our method is practical using real data sets and synthetic data sets.
Protecting Privacy in Incremental Maintenance for Distributed Association Rule Mining.

OLAP on sequence data.
Many kinds of real-life data exhibit logical ordering among their data items and are thus sequential in nature. However, traditional online analytical processing (OLAP) systems and techniques were not designed for sequence data and they are incapable of supporting sequence data analysis. In this paper, we propose the concept of Sequence OLAP, or S-OLAP for short. The biggest distinction of S-OLAP from traditional OLAP is that a sequence can be characterized not only by the attributes ’ values of its constituting items, but also by the subsequence/substring patterns it possesses. This paper studies many aspects related to Sequence OLAP. The concepts of sequence cuboid and sequence data cube are introduced. A prototype S-OLAP system is built in order to validate the proposed concepts. The prototype is able to support “pattern-based” grouping and aggregation, which is currently not supported by any OLAP system. The implementation details of the prototype system as well as experimental results are presented.
Descriptive Schema Semantics%2Dbased Query Answering.
Abstract. We propose the novel concept of “descriptive schema ” (DS). Unlike ordinary database schemas, a DS does not restrict the structure of the underlying database. Rather, it is just a probabilistic description of the structure. When answering keyword queries, DS can be used to improve semantics-based query answering and result ranking. 1 Schema: To have or not to have? Wikipedia is a rich repository of information. However, facilities to exploit the information are still limited. Although typical search WWW search engines such as Google[1] allow users to look for information using keywords, they lack a schema for formulating the queries precisely. Besides hyperlinks among the Wikipedia pages, many pages have Category tags as well as Infoboxes, which can be exploited to perform more sophisticated searches. For example, the DBpedia community makes use of these tags to build a database of RDF triplets, allowing more expressive and precise queries in the form of SPARQL to be used to retrieve useful information [2].
Filtering of false positive microRNA candidates by a clustering%2Dbased approach.

Webformer A Rapid Application Development Toolkit for Writing Ajax Web Form Applications.
Abstract. Web forms are commonly used to capture data on the web. With Asynchronous Javascript and XML (Ajax) programming, interactive web forms can be created. However, Ajax programming is complex in a way that the model-view-controller (MVC) code is not clearly separated. This paper discusses about a MVC-oriented web form development called “Webformer ” that we develop to simplify and streamline web form development with Ajax. We introduce a scripting language called Web Form Application Language (WebFAL) for modeling web forms. Webformer hides the programming complexity by generating Ajax code directly from the web form models. 1
Maintenance of maximal frequent itemsets in large databases.

Security in Outsourcing of Association Rule Mining.

Efficient top%2Dk aggregation of ranked inputs.
A top-k query combines different rankings of the same set of objects and returns the k objects with the highest combined score according to an aggregate function. We bring to light some key observations, which impose two phases that any top-k algorithm, based on sorted accesses, should go through. Based on them, we propose a new algorithm, which is designed to minimize the number of object accesses, the computational cost, and the memory requirements of top-k search with monotone aggregate functions. We provide an analysis for its cost and show that it is always no worse than the baseline “no random accesses ” algorithm in terms of computations, accesses, and memory required. As a side contribution, we perform a space analysis, which indicates the memory requirements of top-k algorithms that only perform sorted accesses. For the case, where the required space exceeds the available memory, we propose disk-based variants of our algorithm. We propose and optimize a multiway top-k join operator, with certain advantages over evaluation trees of binary top-k join operators. Finally, we define and study the computation of top-k cubes and the implementation of roll-up and drill-down operations in such cubes. Extensive experiments with synthetic and real data show that, compared to previous techniques, our method accesses fewer objects, while being orders of magnitude faster.
Discovery of Periodic Patterns in Spatiotemporal Sequences.
In many applications that track and analyze spatiotemporal data, movements obey periodic patterns; the objects follow the same routes (approximately) over regular time intervals. For example, people wake up at the same time and follow more or less the same route to their work everyday. The discovery of hidden periodic patterns in spatiotemporal data could provide unveiling important information to the data analyst. Existing approaches on discovering periodic patterns focus on symbol sequences. However, these methods cannot directly be applied to a spatiotemporal sequence because of the fuzziness of spatial locations in the sequence. In this paper, we define the problem of mining periodic patterns in spatiotemporal data and propose an effective and efficient algorithm for retrieving maximal periodic patterns. In addition, we study two interesting variants of the problem. The first is the retrieval of periodic patterns that are not frequent in the whole history, but during a continuous subinterval of it. The second problem is the discovery of periodic patterns, some instances of which may be shifted or distorted. We demonstrate how our mining technique can be adapted for these variants. Finally, we present a comprehensive experimental evaluation, where we show the effectiveness and efficiency of the proposed techniques.
On mining micro%2Darray data by Order%2DPreserving Submatrix.
We study the problem of pattern-based subspace clustering. Unlike traditional clustering methods that focus on grouping objects with similar values on a set of dimensions, clustering by pattern similarity finds objects that exhibit a coherent pattern of rises and falls in subspaces. Applications of pattern-based subspace clustering include DNA micro-array data analysis, automatic recommendation systems and target marketing systems. Our goal is to devise pattern-based clustering methods that are capable of (1) discovering useful patterns of various shapes, and (2) discovering all significant patterns. We argue that previous solutions in pattern-based subspace clustering do not satisfy both requirements. Our approach is to extend the idea of Order-Preserving Submatrix (or OPSM). We devise a novel algorithm for mining OPSM, show that OPSM can be generalized to cover most existing pattern-based clustering models, and propose a number of extension to the original OPSM model.


Mining periodic patterns with gap requirement from sequences.
We study a problem of mining frequently occurring periodic patterns with a gap requirement from sequences. Given a character sequence S of length L and a pattern P of length l, we consider P a frequently occurring pattern in S if the probability of observing P given a randomly picked length-l subsequence of S exceeds a certain threshold. In many applications, particularly those related to bioinformatics, interesting patterns are periodic with a gap requirement. That is to say, the characters in P should match subsequences of S in such a way that the matching characters in S are separated by gaps of more or less the same size. We show the complexity of the mining problem and discuss why traditional mining algorithms are computationally infeasible. We propose practical algorithms for solving the problem, and study their characteristics. We also present a case study in which we apply our algorithms on some DNA sequences. We discuss some interesting patterns obtained from the case study. 1
Efficient Aggregation of Ranked Inputs.
A top-k query combines different rankings of the same set of objects and returns the k objects with the highest combined score according to an aggregate function. We bring to light some key observations, which impose two phases that any top-k algorithm, based on sorted accesses, should go through. Based on them, we propose a new algorithm, which is designed to minimize the number of object accesses, the computational cost, and the memory requirements of top-k search. Adaptations of our algorithm for search variants (exact scores, on-line and incremental search, top-k joins, other aggregate functions, etc.) are also provided. Extensive experiments with synthetic and real data show that, compared to previous techniques, our method accesses fewer objects, while being orders of magnitude faster. 1
Discovery of Collocation Episodes in Spatiotemporal Data.

A Balanced Ensemble Approach to Weighting Classifiers for Text Classification.

Input Validation for Semi%2Dsupervised Clustering.

Progressive skylining over Web%2Daccessible databases.

SemBiosphere A Semantic Web Approach to Recommending Microarray Clustering Services.
Clustering is a popular method for analyzing microarray data. Given the large number of clustering algorithms being available, it is difficult to identify the most suitable ones for a particular task. It is also difficult to locate, download, install and run the algorithms. This paper describes a matchmaking system, SemBiosphere, which solves both problems. It recommends clustering algorithms based on some minimal user requirement inputs and the data properties. An ontology was developed in OWL, an expressive ontological language, for describing what the algorithms are and how they perform, in addition to how they can be invoked. This allows machines to “understand ” the algorithms and make the recommendations. The algorithm can be implemented by different groups and in different languages, and run on different platforms at geographically distributed sites. Through the use of XML-based web services, they can all be invoked in the same standard way. The current clustering services were transformed from the non-semantic web services of the Biosphere system, which includes a variety of algorithms that have been applied to microarray gene expression data analysis. New algorithms can be incorporated into the system without too much effort. The SemBiosphere system and the complete clustering ontology can be accessed at
Progressive skylining over Web%2Daccessible databases.

WSIPL An XML scripting language for integrating web service data and applications.

Advances in Knowledge Discovery and Data Mining

On Discovery of Extremely Low%2DDimensional Clusters using Semi%2DSupervised Projected Clustering.
Recent studies suggest that projected clusters with extremely low dimensionality exist in many real datasets. A number of projected clustering algorithms have been proposed in the past several years, but few can identify clusters with dimensionality lower than 10% of the total number of dimensions, which are commonly found in some real datasets such as gene expression profiles. In this paper we propose a new algorithm that can accurately identify projected clusters with relevant dimensions as few as 5% of the total number of dimensions. It makes use of a robust objective function that combines object clustering and dimension selection into a single optimization problem. The algorithm can also utilize domain knowledge in the form of labeled objects and labeled dimensions to improve its clustering accuracy. We believe this is the first semi-supervised projected clustering algorithm. Both theoretical analysis and experimental results show that by using a small amount of input knowledge, possibly covering only a portion of the underlying classes, the new algorithm can be further improved to accurately detect clusters with only 1% of the dimensions being relevant. The algorithm is also useful in getting a target set of clusters when there are multiple possible groupings of the objects.
On Mining Micro%2Darray data by Order%2DPreserving Submatrix.
We study the problem of pattern-based subspace clustering. Unlike traditional clustering methods that focus on grouping objects with similar values on a set of dimensions, clustering by pattern similarity finds objects that exhibit a coherent pattern of rises and falls in subspaces. Applications of pattern-based subspace clustering include DNA micro-array data analysis, automatic recommendation systems and target marketing systems. Our goal is to devise pattern-based clustering methods that are capable of (1) discovering useful patterns of various shapes, and (2) discovering all significant patterns. We argue that previous solutions in pattern-based subspace clustering do not satisfy both requirements. Our approach is to extend the idea of Order-Preserving Submatrix (or OPSM). We devise a novel algorithm for mining OPSM, show that OPSM can be generalized to cover most existing pattern-based clustering models, and propose a number of extension to the original OPSM model.
Mining Frequent Spatio%2DTemporal Sequential Patterns.
Many applications track the movement of mobile objects, which can be represented as sequences of timestamped locations. Given such a spatio-temporal series, we study the problem of discovering sequential patterns, which are routes frequently followed by the object. Sequential pattern mining algorithms for transaction data are not directly applicable for this setting. The challenges to address are (i) the fuzziness of locations in patterns, and (ii) the identification of non-explicit pattern instances. In this paper, we define pattern elements as spatial regions around frequent line segments. Our method first transforms the original sequence into a list of sequence segments, and detects frequent regions in a heuristic way. Then, we propose algorithms to find patterns by employing a newly proposed substring tree structure and improving Apriori technique. A performance evaluation demonstrates the effectiveness and efficiency of our approach. 1
Cross Table Cubing Mining Iceberg Cubes from Data Warehouses.

Mining Periodic Patterns with Gap Requirement from Sequences.
We study a problem of mining frequently occurring periodic patterns with a gap requirement from sequences. Given a character sequence S of length L and a pattern P of length l, we consider P a frequently occurring pattern in S if the probability of observing P given a randomly picked length-l subsequence of S exceeds a certain threshold. In many applications, particularly those related to bioinformatics, interesting patterns are periodic with a gap requirement. That is to say, the characters in P should match subsequences of S in such a way that the matching characters in S are separated by gaps of more or less the same size. We show the complexity of the mining problem and discuss why traditional mining algorithms are computationally infeasible. We propose practical algorithms for solving the problem, and study their characteristics. We also present a case study in which we apply our algorithms on some DNA sequences. We discuss some interesting patterns obtained from the case study. 1
CLUSTAG hierarchical clustering and graph methods for selecting tag SNPs.

Efficient Algorithms for Mining and Incremental Update of Maximal Frequent Sequences.

Indexing Useful Structural Patterns for XML Query Processing.
Abstract—Queries on semistructured data are hard to process due to the complex nature of the data and call for specialized techniques. Existing path-based indexes and query processing algorithms are not efficient for searching complex structures beyond simple paths, even when the queries are high-selective. We introduce the definition of minimal infrequent structures (MIS), which are structures that 1) exist in the data, 2) are not frequent with respect to a support threshold, and 3) all substructures of them are frequent. By indexing the occurrences of MIS, we can efficiently locate the high-selective substructures of a query, improving search performance significantly. An efficient data mining algorithm is proposed, which finds the minimal infrequent structures. Their occurrences in the XML data are then indexed by a lightweight data structure and used as a fast filter step in query evaluation. We validate the efficiency and applicability of our methods through experimentation on both synthetic and real data. Index Terms—Query processing, XML/XSL/RDF, mining methods and algorithms, document indexing. 1
Fast and Exact Warping of Time Series Using Adaptive Segmental Approximations.
Abstract. Similarity search is a core module of many data analysis tasks, including search by example, classification, and clustering. For time series data, Dynamic Time Warping (DTW) has been proven a very effective similarity measure, since it minimizes the effects of shifting and distortion in time. However, the quadratic cost of DTW computation to the length of the matched sequences makes its direct application on databases of long time series very expensive. We propose a technique that decomposes the sequences into a number of segments and uses cheap approximations thereof to compute fast lower bounds for their warping distances. We present several, progressively tighter bounds, relying on the existence or not of warping constraints. Finally, we develop an index and a multi-step technique that uses the proposed bounds and performs two levels of filtering to efficiently process similarity queries. A thorough experimental study suggests that our method consistently outperforms state-of-the-art methods for DTW similarity search.
Identifying Projected Clusters from Gene Expression Profiles.
In microarray gene expression data, clusters may hide in certain subspaces. For example, a set of co-regulated genes may have similar expression patterns in only a subset of the samples in which certain regulating factors are present. Their expression patterns could be dissimilar when measuring in the full input space. Traditional clustering algorithms that make use of such similarity measurements may fail to identify the clusters. In recent years a number of algorithms have been proposed to identify this kind of projected clusters, but many of them rely on some critical parameters whose proper values are hard for users to determine. In this paper a new algorithm that dynamically adjusts its internal thresholds is proposed. It has a low dependency on user parameters while allowing users to input some domain knowledge should they be available. Experimental results show that the algorithm is capable of identifying some interesting projected clusters.
SF%2DTree An Efficient and Flexible Structure for Estimating Selectivity of Simple Path Expressions with Statistical Accuracy Guarantee.

Processing Ad%2DHoc Joins on Mobile Devices.
Abstract. Mobile devices are capable of retrieving and processing data from remote databases. In a wireless data transmission environment, users are typically charged by the size of transferred data, rather than the amount of time they stay connected. We propose algorithms that join information from non-collaborative remote databases on mobile devices. Our methods minimize the data transferred during the join process, by also considering the limitations of mobile devices. Experimental results show that our approach can perform join processing on mobile devices effectively. 1
Mining%2C indexing%2C and querying historical spatiotemporal data.
Abstract—Given a large spatio-temporal database of events, where each event consists of the fields event ID, time, location, and event type, mining spatio-temporal sequential patterns identifies significant event-type sequences. Such spatio-temporal sequential patterns are crucial to the investigation of spatial and temporal evolutions of phenomena in many application domains. Recent research literature has explored the sequential patterns on transaction data and trajectory analysis on moving objects. However, these methods cannot be directly applied to mining sequential patterns from a large number of spatio-temporal events. Two major research challenges still remain: 1) the definition of significance measures for spatio-temporal sequential patterns to avoid spurious ones and 2) the algorithmic design under the significance measures, which may not guarantee the downward closure property. In this paper, we propose a sequence index as the significance measure for spatio-temporal sequential patterns, which is meaningful due to its interpretability using spatial statistics. We propose a novel algorithm called Slicing-STS-Miner to tackle the algorithmic design challenge using the spatial sequence index, which does not preserve the downward closure property. We compare the proposed algorithm with a simple algorithm called STS-Miner that utilizes the weak monotone property of the sequence index. Performance evaluations using both synthetic and real-world data sets show that the Slicing-STS-Miner is an order of magnitude faster than STS-Miner for large data sets. Index Terms—Spatio-temporal sequential pattern, density ratio, sequence index, slicing, performance. Ç 1
Fast mining of spatial collocations.

Discovering Partial Periodic Patterns in Discrete Data Sequences.
Abstract. The problem of partial periodic pattern mining in a discrete data sequence is to find subsequences that appear periodically and frequently in the data sequence. Two essential subproblems are the efficient mining of frequent patterns and the automatic discovery of periods that correspond to these patterns. Previous methods for this problem in event sequence databases assume that the periods are given in advance or require additional database scans to compute periods that define candidate patterns. In this work, we propose a new structure, the abbreviated list table (ALT), and several efficient algorithms to compute the periods and the patterns, that require only a small number of passes. A performance study is presented to demonstrate the effectiveness and efficiency of our method. 1
Discovering Minimal Infrequent Structures from XML Documents.

A web services choreography scenario for interoperating bioinformatics applications.

An Efficient and Scalable Algorithm for Clustering XML Documents by Structure.
Abstract—With the standardization of XML as an information exchange language over the net, a huge amount of information is formatted in XML documents. In order to analyze this information efficiently, decomposing the XML documents and storing them in relational tables is a popular practice. However, query processing becomes expensive since, in many cases, an excessive number of joins is required to recover information from the fragmented data. If a collection consists of documents with different structures (for example, they come from different DTDs), mining clusters in the documents could alleviate the fragmentation problem. We propose a hierarchical algorithm (S-GRACE) for clustering XML documents based on structural information in the data. The notion of structure graph (s-graph) is proposed, supporting a computationally efficient distance metric defined between documents and sets of documents. This simple metric yields our new clustering algorithm which is efficient and effective, compared to other approaches based on tree-edit distance. Experiments on real data show that our algorithm can discover clusters not easily identified by manual inspection. Index Terms—Data mining, clustering, XML, semistructured data, query processing. 1
HARP A Practical Projected Clustering Algorithm.
Abstract—In high-dimensional data, clusters can exist in subspaces that hide themselves from traditional clustering methods. A number of algorithms have been proposed to identify such projected clusters, but most of them rely on some user parameters to guide the clustering process. The clustering accuracy can be seriously degraded if incorrect values are used. Unfortunately, in real situations, it is rarely possible for users to supply the parameter values accurately, which causes practical difficulties in applying these algorithms to real data. In this paper, we analyze the major challenges of projected clustering and suggest why these algorithms need to depend heavily on user parameters. Based on the analysis, we propose a new algorithm that exploits the clustering status to adjust the internal thresholds dynamically without the assistance of user parameters. According to the results of extensive experiments on real and synthetic data, the new method has excellent accuracy and usability. It outperformed the other algorithms even when correct parameter values were artificially supplied to them. The encouraging results suggest that projected clustering can be a practical tool for various kinds of real applications. Index Terms—Data mining, mining methods and algorithms, clustering, bioinformatics. 1
Optimization in Data Cube System Design.
Abstract. The design of an OLAP system for supporting real-time queries is one of the major research issues. One approach is to use data cubes, which are materialized precomputed multidimensional views of data in a data warehouse. We can derive a set of data cubes to answer each frequently asked query directly. However, there are two practical problems: (1) the maintenance cost of the data cubes, and (2) the query cost to answer those queries. Maintaining a data cube requires disk storage and CPU computation, so the maintenance cost is related to the total size as well as the total number of data cubes materialized. In most cases, materializing all data cubes is impractical. The maintenance cost may be reduced by merging some data cubes. However, the resulting larger data cubes will increase the query cost of answering some queries. If the bounds on the maintenance cost and the query cost are too strict, we help the user decide which queries to be sacrificed and not taken into consideration. We have defined an optimization problem in data cube system design. Given a maintenance-cost bound, a query-cost bound and a set of frequently asked queries, it is necessary to determine a set of data cubes such that the system can answer a largest subset of the queries without violating the two bounds. This is an NP-hard problem. We propose approximate Greedy algorithms GR, 2GM and 2GMM, which are shown to be both effective and efficient by experiments done on a census data set and a forest-cover-type data set.
Identifying projected clusters from gene expression profiles.
In microarray gene expression data, clusters may hide in certain subspaces. For example, a set of co-regulated genes may have similar expression patterns in only a subset of the samples in which certain regulating factors are present. Their expression patterns could be dissimilar when measuring in the full input space. Traditional clustering algorithms that make use of such similarity measurements may fail to identify the clusters. In recent years a number of algorithms have been proposed to identify this kind of projected clusters, but many of them rely on some critical parameters whose proper values are hard for users to determine. In this paper a new algorithm that dynamically adjusts its internal thresholds is proposed. It has a low dependency on user parameters while allowing users to input some domain knowledge should they be available. Experimental results show that the algorithm is capable of identifying some interesting projected clusters.
A highly%2Dusable projected clustering algorithm for gene expression profiles.
Projected clustering has become a hot research topic due to its ability to cluster high-dimensional data. However, most existing projected clustering algorithms depend on some critical user parameters in determining the relevant attributes of each cluster. In case wrong parameter values are used, the clustering performance will be seriously degraded. Unfortunately, correct parameter values are rarely known in real datasets. In this paper, we propose a projected clustering algorithm that does not depend on user inputs in determining relevant attributes. It responds to the clustering status and adjusts the internal thresholds dynamically. From experimental results, our algorithm shows a much higher usability than the other projected clustering algorithms used in our comparison study. It also works well with a gene expression dataset for studying lymphoma. The high usability of the algorithm and the encouraging results suggest that projected clustering can be a practical tool for analyzing gene expression profiles.
Maintenance of Partial%2DSum%2DBased Histograms.
This paper introduces an efficient method for the maintenance of wavelet-based histograms built on partial sums. Wavelet-based histograms can be constructed from either raw data distributions or partial sums. The two construction methods have their own merits. Previous works have only focused on the maintenance of raw-data-based histograms. However, it is highly inefficient to apply directly their techniques to partial-sum-based histograms because a single data update would trigger changes of multiple partial sums, which in turn, would trigger large amounts of computation on the changes of the wavelet decomposition.
Approximate String Matching in DNA Sequences.
Approximate string matching on large DNA sequences data is very important in bioinformatics. Some studies have shown that suffix tree is an efficient data structure for approximate string matching. It performs better than suffix array if the data structure can be stored entirely in the memory. However, our study find that suffix array is much better than suffix tree for indexing the DNA sequences since the data structure has to be created and stored on the disk due to its size. We propose a novel auxiliary data structure which greatly improves the efficiency of suffix array in the approximate string matching problem in the external memory model. The second problem we have tackled is the parallel approximate matching in DNA sequence. We propose 2 novel parallel algorithms for this problem and implement them on a PC cluster. The result shows that when the error allowed is small, a direct partitioning of the array over the machines in the cluster is a more efficient approach. On the other hand, when the error allowed is large, partitioning the data over the machines is a better approach.
Similarity Search in Sets and Categorical Data Using the Signature Tree.
Data mining applications analyze large collections of set data and high dimensional categorical data. Search on these data types is not restricted to the classic problems of mining association rules and classification, but similarity search is also a frequently applied operation. Access methods for multidimensional numerical data are inappropriate for this problem and specialized indexes are needed. We propose a method that represents set data as bitmaps (signatures) and organizes them into a hierarchical index, suitable for similarity search and other related query types. In contrast to a previous technique, the signature tree is dynamic and does not rely on hardwired constants. Experiments with synthetic and real datasets show that it is robust to different data characteristics, scalable to the database size and efficient for various queries. 1
Evaluation of Iceberg Distance Joins.

A Filter Index for Complex Queries on Semi%2Dstructured Data.

Web Services Oriented Data Processing and Integration.
Data processing and integration on heterogeneous data sources often require intensive human resources. As Web Services standardize the programmatic interfaces for application to application communication, it has gained a considerable momentum as a mean to facilitate processing and integrating heterogeneous data sources. To take full advantage of Web Services, we proposed a Web Services oriented approach which all operations and data sources are exposed as Web Services. Bases on that approach, we also designed a novel declarative scripting language, called WSIPL (Web Services Integration and Processing Language), which provides specially designed language constructs for integrating and processing Web Services systematically at minimal programming efforts. Finally, we proposed a reference architecture, with application examples on WSIPL implementation to demonstrate the effectiveness on our work.
Efficient Algorithms for Incremental Update of Frequent Sequences.
Agrawal and Srikant first put forward the problem of mining frequently occurring se-  quences from a customer database [1]. In their model, a customer database consists of a set  of sequences. Each sequence is a chronologically ordered set of transactions (or itemsets).
An Efficient Algorithm for Incremental Update of Concept Spaces.
The vocabulary problem in information retrieval arises be-  cause authors and indexers often use different terms for the same con-  cept. A thesaurus defines mappings between different but related terms.

Enhancing Effectiveness of Outlier Detections for Low Density Patterns.

DIRECT a system for mining data value conversion rules from disparate data sources.
may be quoted without explicit permission, provided that full credit including © notice is given to the source. This paper also can be downloaded without charge from the
Parallel Mining of Outliers in Large Database.
Data mining is a new, important and fast growing database application. Outlier  (exception) detection is one kind of data mining, which can be applied in a variety  of areas like monitoring of credit card fraud and criminal activities in electronic  commerce. With the ever-increasing size and attributes (dimensions) of database,  previously proposed detection methods for two dimensions are no longer applicable.

Automatic construction of online catalog topologies.

A lattice%2Dbased approach for I%2FO efficient association rule mining.

Knowledge Discovery and Data Mining %2D PAKDD 2001


Mining Confident Rules Without Support Requirement.
An open problem is to find all rules that satisfy a minimum confidence but not necessarily a minimum support. Without the support requirement, the classic support-based pruning strat,egy is inapplicable. The problem demands a confidencebased pruning strategy. In particular, the following monotonicity of confidence, called the universal-existential upzuard closure, holds: if a rule of size k is confident (for the given minimum confidence), for every other attribute not in the rule, some specialization of size k + 1 using the attribute must be confident. Like the support-based pruning, the bottleneck is at the memory that often is too small to store the candidates required for search. We implement this strategy on disk and study its performance. 1.
An Empirical Study on the Visual Cluster Validation Method with Fastmap.

Automatic Construction of Online Catalog Topologies.

FFS %2D An I%2FO%2DEfficient Algorithm for Mining Frequent Sequences.


Indexing Attributes and Reordering Profiles for XML Document Filtering and Information Delivery.

A Cube Model and Cluster Analysis for Web Access Sessions.

An Adaptive Algorithm for Mining Association Rules on Shared%2DMemory Parallel Machines.
Mining association rules from large databases is very costly. We propose to develop parallel algorithms for this task on shared-memory multiprocessor (SMP). All proposed parallel algorithms for other paradigms follow the conventional level-wise approach : they need as many iterations as the length of the maximum large itemset. To make matter worse, they impose a synchronization in every iteration which would cause serious I/O contention on shared-memory parallel system. An adaptive asynchronous parallel mining algorithm APM has been proposed for SMP. All processors generate candidates dynamically and count itemset supports independently without synchronization. Two optimization techniques have been proposed for the reduction of database scanning and the number of candidates. The algorithm APM has been implemented on a Sun Enterprise 4000 shared-memory multiprocessor with 12 nodes. The experiments show that the optimizations have very good effects and APM has a substantial lead in perfo...
Pervasive Multimedia Markup Language %28PMML%29 an XML%2Dbased multimedia content specification for pervasive access.

Towards the building of a dense%2Dregion%2Dbased OLAP system.
On-line Analytical Processing (OLAP) has become a very useful tool in decision support  systems built on data warehouses. ROLAP (Relational OLAP) and MOLAP (Multidimensional  OLAP) are two popular approaches for building OLAP systems. These two  approaches have very different performance characteristics: MOLAP has good query performance  but bad space efficiency, while ROLAP can be built on mature RDBMS technology  but it needs sizable indices to support it. Many data warehouses contain many small clustered  multidimensional data (dense regions), with sparse points scattered around in the  rest of the space. For these databases, we propose that the dense regions be located and  separated from the sparse points. The dense regions can subsequently be represented by  small MOLAPs, while the sparse points are put in a ROLAP table. Thus the MOLAP  and ROLAP approaches can be integrated in one structure to build a high performance  and space efficient dense-region-based data cube. In this pa...
An Adaptive Algorithm for Mining Association Rules on Shared%2DMemory Parallel Machines.
Mining association rules from large databases is very costly. We propose to develop parallel algorithms for this task on shared-memory multiprocessor (SMP). All proposed parallel algorithms for other paradigms follow the conventional level-wise approach : they need as many iterations as the length of the maximum large itemset. To make matter worse, they impose a synchronization in every iteration which would cause serious I/O contention on shared-memory parallel system. An adaptive asynchronous parallel mining algorithm APM has been proposed for SMP. All processors generate candidates dynamically and count itemset supports independently without synchronization. Two optimization techniques have been proposed for the reduction of database scanning and the number of candidates. The algorithm APM has been implemented on a Sun Enterprise 4000 shared-memory multiprocessor with 12 nodes. The experiments show that the optimizations have very good effects and APM has a substantial lead in perfo...
Discovering and reconciling value conflicts for numerical data integration.
The built-up in Information Technology capital fueled by the Internet and cost-e#ectiveness of new telecommunications technologies has led to a proliferation of information systems that are in dire need to exchange information but incapable of doing so due to the lack of semantic interoperability. It is now evident that physical connectivity (the ability to exchange bits and bytes) is no longer adequate: the integration of data from autonomous and heterogeneous systems calls for the prior identification and resolution of semantic conflicts that may be present. Unfortunately, this requires the system integrator to sift through the data from disparate systems in a painstaking manner. We suggest that this process can be partially automated by presenting a methodology and technique for the discovery of potential semantic conflicts as well as the underlying data transformation needed to resolve the conflicts. Our methodology begins by classifying data value conflicts into two categories: context independent and context dependent. While context independent conflicts are usually caused by unexpected errors, the context dependent conflicts are primarily a result of the heterogeneity of underlying data sources. To facilitate data integration, data value conversion rules are proposed to describe the quantitative relationships among data values involving context dependent conflicts. A general approach is proposed to discover data value conversion rules from the data. The approach consists of the five major steps: relevant attribute analysis, candidate model selection, conversion function generation, conversion function selection and conversion rule formation. It is being implemented in a prototype system, DIRECT, for business data using statistics based techniques. Preliminary stu...
Exploiting the Duality of Maximal Frequent Itemsets and Minimal Infrequent Itemsets for I%2FO Efficient Association Rule Mining.

An Interactive Approach to Building Classification Models by Clustering and Cluster Validation.

Density%2DBased Mining of Quantitative Association Rules.

Text%2DSource Discovery and GlOSS Update in a Dynamic Web.

An Optimization Problem in Data Cube System Design.
. In an OLAP system, we can use data cubes (precomputed  multidimensional views of data) to support real-time queries.  To reduce the maintenance cost, which is related to the number  of cubes materialized, some cubes can be merged, but the resulting  larger cubes will increase the response time of answering some  queries. In order to satisfy the maintenance bound and response  time bound given by the user, we may have to sacrifice some of  the queries and not to take them into our consideration. The optimization  problem in the data cube system design is to optimize  an initial set of cubes such that the system can answer a maximum  number of queries and satisfy the bounds. This is an NP-complete  problem. Approximate algorithms Greedy Removing and 2-Greedy  Merging are proposed. Experiments have been done on a census  database and the results show that our approach is both effective  and efficient.  1 Introduction  1.1 DSS and OLAP  With the advancement of data warehousing technology...
Distributed and Scalable XML Document Processing Architecture for E%2DCommerce Systems.

A Semantic Similarity Approach to Electronic Document Modeling and Integration.

Using Contextual Semantics to Automate the Web Document Search and Analysis.

Anchor point indexing in Web document retrieval.
Traditional WWW search engines, such as Alta Vista, index and recommend individual  Web pages to assist users in locating relevant documents. As the Web grows, however, the  number of matching pages increases at a tremendous rate. Users are often overwhelmed by  the large answer set recommended by the search engines. Also, if a matching document is  a hypertext, the document structure is destroyed and the individual pages that compose  the document are returned instead. The logical starting point of the hyper-document is  thus hidden among the large basket of matching pages. Users need to spend a lot of effort  browsing through the pages to locate the starting point, a very time consuming process.  This paper studies the anchor point indexing problem. The set of anchor points of a given  user query is a small set of key pages from which the larger set of documents that are relevant  to the query can be easily reached. The use of anchor points help solve the problems of huge  answer set...
Efficient Rule%2DBased Attribute%2DOriented Induction for Data Mining.
. Data mining has become an important technique which has tremendous potential in many commercial and industrial applications. Attribute-oriented induction is a powerful mining technique and has been successfully implemented in the data mining system DBMiner [17]. However, its induction capability is limited by the unconditional concept generalization. In this paper, we extend the concept generalization to rule-based concept hierarchy, which enhances greatly its induction power. When previously proposed induction algorithm is applied to the more general rule-based case, a problem of induction anomaly occurs which impacts its efficiency. We have developed an efficient algorithm to facilitate induction on the rule-based case which can avoid the anomaly. Performance studies have shown that the algorithm is superior than a previously proposed algorithm based on backtracking.  Keywords: data mining, knowledge discovery in databases, rule-based concept generalization, rule-based concept hier...
Requirement%2DBased Data Cube Schema Design.
On-line analytical processing (OLAP) requires efficient processing of complex decision support queries over very large databases. It is well accepted that pre-computed data cubes can help reduce the response time of such queries dramatically. A very important design issue of an efficient OLAP system is therefore the choice of the right data cubes to materialize. We call this problem the data cube schema design problem. In this paper we show that the problem of finding an optimal data cube schema for an OLAP system with limited memory is NP-hard. As a more computationally efficient alternative, we propose a greedy approximation algorithm cMP and its variants. Algorithm cMP consists of two phases. In the first phase, an initial schema consisting of all the cubes required to efficiently answer the user queries is formed. In the second phase, cubes in the initial schema are selectively merged to satisfy the memory constraint. We show that cMP is very effective in prunning the search space ...
DROLAP %2D A Dense%2DRegion Based Approach to On%2DLine Analytical Processing.
ROLAP (Relational OLAP) and MOLAP (Multidimensional OLAP) are two opposing techniques for building On-line Analytical Processing (OLAP) systems. MOLAP has good query performance but suffers when the data distribution in the multidimensional data cube is sparse. ROLAP can be built on mature RDBMS technology but its performance is not as competitive. Many data warehouses contain sparse but clustered multidimensional data. We propose a dense-region-based OLAP (DROLAP) system which surpasses both ROLAP and MOLAP in space efficiency and query performance. DROLAP applies the MOLAP approach on the dense regions discovered in the data, and handles the remaining small percentage of sparse points with the ROLAP approach. The core of building a DROLAP system lies in the mining of dense regions in a data cube. We have defined the dense region mining problem as an optimization problem. We show that conventional clustering techniques are not suitable for this problem, and have developed an efficient...
A Fast Algorithm for Density%2DBased Clustering in Large Database.

LGen %2D A Lattice%2DBased Candidate Set Generation Algorithm for I%2FO Efficient Association Rule Mining.
Most algorithms for association rule mining are variants of the basic Apriori algorithm  [1]. One characteristic of these Apriori-based algorithms is that candidate itemsets are  generated in rounds, with the size of the itemsets incremented by one per round. The  number of database scans required by Apriori-based algorithms thus depends on the size of  the largest large itemsets. In this paper we devise a more general candidate set generation  algorithm, LGen, which generates candidate itemsets of multiple sizes during each database  scan. We show that, given a reasonable set of suggested large itemsets, LGen can significantly  reduce the number of I/O passes required. In the best cases, only two passes are sufficient  to discover all the large itemsets irrespective of the size of the largest ones.  Keywords: Data mining, association rules, lattice, Apriori, LGen  1 Introduction  Data mining has recently attracted considerable attention from database practitioners and researchers beca...
Effect of Data Distribution in Parallel Mining of Associations.
Association rule mining is an important new problem in data mining. It has crucial applications in decision support  and marketing strategy. We proposed an efficient parallel algorithm for mining association rules on a distributed  share-nothing parallel system. Its efficiency is attributed to the incorporation of two powerful candidate set pruning  techniques. The two techniques, distributed and global prunings, are sensitive to two data distribution characteristics:  data skewness and workload balance. The prunings are very effective when both the skewness and balance are high.  We have implemented FPM on an IBM SP2 parallel system. The performance studies show that FPM outperforms  CD consistently, which is a parallel version of the representative Apriori algorithm [2]. Also, the results have validated  our observation on the effectiveness of the two pruning techniques with respect to the data distribution characteristics.  Furthermore, it shows that FPM has nice scalability and par...
Oblivious routing for LC permutations on hypercubes.

Recommending Anchor Points in Structure%2DPreserving Hypertext Document Retrieval.


Effect of Data Skewness in Parallel Mining of Association Rules.
An efficient parallel algorithm FPM (Fast Parallel Mining) for mining association rules on a shared-nothing parallel system has been proposed. It adopts the count distribution approach and has incorporated two powerful candidate pruning techniques, i.e., distributed pruning and global pruning. It has a simple communication scheme which performs only one round of message exchange in each iteration. We found that the two pruning techniques are very sensitive to data skewness, which describes the degree of non-uniformity of the itemset distribution among the database partitions. Distributed pruning is very effective when data skewness is high. Global pruning is more effective than distributed pruning even for the mild data skewness case. We have implemented the algorithm on an IBM SP2 parallel machine. The performance studies confirm our observation on the relationship between the effectiveness of the two pruning techniques and data skewness. It has also shown that FPM outp...
Asynchronous Parallel Algorithm for Mining Association Rules on a Shared%2DMemory MultiPprocessors.

Is Sampling Useful in Data Mining%3F A Case in the Maintenance of Discovered Association Rules.
By nature, sampling is an appealing technique for data mining, because approximate solutions in most cases may already be of great satisfaction to the need of the users. We attempt to use sampling techniques to address the problem of maintaining discovered association rules. Some studies have been done on the problem of maintaining the discovered association rules when updates are made to the database. All proposed methods must examine not only the changed part but also the unchanged part in the original database, which is very large, and hence take much time. Worse yet, if the updates on the rules are performed frequently on the database but the underlying rule set has not changed much, then the effort could be mostly wasted. In this paper, we devise an algorithm which employs sampling techniques to estimate the difference between the association rules in a database before and after the database is updated. The estimated difference can be used to determine whether we should update the...
Discovering user access patterns on the World Wide Web.
this paper, we focus on the techniques in designing a level 4 Web tool. A system design and its architecture is proposed. In particular, we study the problem of constructing user profiles from user access history.

A General Incremental Technique for Maintaining Discovered Association Rules.
A more general incremental updating technique is developed for maintaining the association rules discovered in a database in the cases including insertion, deletion, and modification of transactions in the database. A previously proposed algorithm FUP can only handle the maintenance problem in the case of insertion. The proposed algorithm FUP2 makes use of the previous mining result to cut down the cost of finding the new rules in an updated database. In the insertion only case, FUP2 is equivalent to FUP. In the deletion only case, FUP2 is a complementary algorithm of FUP which is very efficient when the deleted transactions is a small part of the database, which is the most applicable case. In the general case, FUP2 can efficiently update the discovered rules when new transactions are added to a transaction database, and obsolete transactions are removed from it. The proposed algorithm has been implemented and its performance is studied and compared with the best algorithms for mining...
Maintenance of Discovered Association Rules When to update%3F
In this paper, we devise an algorithm with which we can estimate the difference between the association rules in a database before and after it is updated. The estimated difference can be used to determine whether we update the mined association rules or not. If the estimated difference is large, then it is time to update the mined association rules in order to discover and learn the new rules and discard the old ones. If the estimated difference is small, then the rules in the original database is still a good approximation for those in the updated database. We do not have to spend the resources to update the rules. We can accumulate more updates before actually updating the rules, thereby avoiding the overheads of updating the rules too frequently.  1 Introduction  Data mining has been attracting much attention from practitioners and researchers in recent years. Combining techniques from the fields of machine learning, statistics and databases, data mining enables us to find out usef...
Discovering and Reconciling Semantic Conflicts A Data Mining Perspective.
Current approaches to semantic interoperability require human intervention in detecting potential con#icts and in defining how those con#icts maybe resolved. This is a major impedance to achieving &#034;logical connectivity&#034;, especially when the number of disparate sources is large. In this paper, we demonstrate that the detection and reconciliation of semantic conflicts can be automated using tools and techniques developed by the data mining community. We describe a process for discovering such rules that represent the relationships among semanticaly related attributes and illustrate the effectiveness of our approach with examples. Keywords Database Integration, Data Mining, Regression Analysis, Semantic Conflicts 1 INTRODUCTION Avariety of online information sources and receivers #i.e., users and applications has emerged at an unprecedented rate in the last few years, contributed in large part by the exponential growth of the Internet as well as advances in telecommunications technolog...
Intelligent Agents for Matching Information Providers and Consumers on the World%2DWide%2DWeb.

Incremental Updates of Discovered Multi%2DLevel Association Rules.

Maintenance of Discovered Association Rules in Large Databases An Incremental Updating Technique.
An incremental updating technique is developed for maintenance of the association rules discovered by database mining. There have been many studies on efficient discovery of association rules in large databases. However, it is nontrivial to maintain such discovered rules in large databases because a database may allow frequent or occasional updates and such updates may not only invalidate some existing strong association rules but also turn some weak rules into strong ones. In this study, an incremental updating technique is proposed for efficient maintenance of dis- covered association rules when new transaction data are added to a transaction database.
Maintenance of Discovered Knowledge A Case in Multi%2DLevel Association Rules.
Many knowledge discovery (kdd) systems need to spend substantial amount of effort to search for rules  and patterns within large amount of data. After some natural evolutions, as a consequence of updates  applied to their databases, these systems must update their previously discovered knowledge to reflect the  current state of their databases. The straight forward approach of re-running the discovery process on  the whole updated database to re-discover the rules and patterns is not cost-effective in general, and is  unacceptable in many cases. We have studied the problem of updating discovered association rules and  found that it is nontrivial, because updates may not only invalidate some existing strong association rules  but also turn some weak rules into strong ones. An incremental technique and a fast algorithm FUP  have been proposed previously for the update of discovered single-level association rules. In this study,  a more efficient algorithm FUP*, which generates a smaller ...
A Fast Distributed Algorithm for Mining Association Rules.
With the existence of many large transaction databases, the huge amounts of data, the high scalability of distributed systems, and the easy partition and distribution of a centralized database, it is important to investigate efficient methods for distributed mining of association rules. This study discloses some interesting relationships between locally large and globally large itemsets and proposes an interesting distributed association rule mining algorithm, FDM (Fast Distributed Mining of association rules), which generates a small number of candidate sets and substantially reduces the number of messages to be passed at mining association rules. Our performance study shows that FDM has a superior performance over the direct application of a typical sequential algorithm. Further performance enhancement leads to a few variations of the algorithm.
Efficient Mining of Association Rules in Distributed Databases.
Many sequential algorithms have been proposed for mining of association rules. However, very little work has been done in mining association rules in distributed databases. A direct application of sequential algorithms to distributed databases is not effective, because it requires a large amount of communication overhead. In this study, an efficient algorithm, DMA, is proposed. It generates a small number of candidate sets and requires only O(n) messages for support count exchange for each candidate set, where n is the number of sites in a distributed database. The algorithm has been implemented on an experimental test bed and its performance is studied. The results show that DMA has superior performance when comparing with the direct application of a popular sequential algorithm in distributed databases.
Maintenance of Discovered Knowledge A Strategy for Updating Association Rules %28Abstract%29.

A Case%2DBased Reasoning Approach for Associative Query Answering.
. Traditional DBMS only retrieves data that perfectly match the user query and also requires the user to know the detailed database schema. Often, it is desirable to obtain additional relevant information to a query. In this paper, we present a method to provide useful information to the user that he does not explicitly asked for. Such domain specific knowledge associated to a given query depends on each user&#039;s goal and knowledge. Thus, we propose using the Case Based Reasoning paradigm to integrate past user experience and the current goal in order to guide the association. Useful associations are incrementally acquired from observations of past experiences and adapted to answer the current user query. A prototype of the associative query answering system using the proposed method has been implemented on top of the cooperative database system, CoBase, at UCLA. Our preliminary experimental results reveal that it is a feasible and scalable method for association control. 1 Introduction ...
A Transaction Replication Scheme for a Replicated Database with Node Autonomy.
Many proposed protocols for replicated databases consider centralized control of each transaction so that given a transaction, some site will monitor the remote data access and transaction commit. We consider the approach of broadcasting transactions to remote sites and handling these transactions in their complete form at each site. We consider data of two types: shared-private data and public data and show that transactions working only on shared-private data can be executed under a local concurrency control protocol. We assume a synchronized network with possibilities of partition failures. We show that in our scheme transaction execution can be managed with less communication delay compared to centralized transaction control.  1 Motivation  Many replicated distributed database protocols manage the execution of a given transaction at one site, accessing local and remote data copies for its operations, and organize the commit or abort of the transaction from that site. We refer to th...
Site Optimal termination Protocols for a Distributed Database under Network Partitioning.

Site Optimal Termination Protocols for a Distributed Database under Network Partitioning.

